# 法1
# class Solution(object):
#     def duplicateZeros(self, arr):
#         """
#         :type arr: List[int]
#         :rtype: None Do not return anything, modify arr in-place instead.
#         """
#         n = len(arr)
#         index = 0
#         count = 0
#         while index < n - count:
#             if arr[index] == 0:
#                 arr[index] += count * 10
#                 count += 1
#             else:
#                 arr[index] += count * 10
#             index += 1
#         for k in range(index, n):
#             arr[k] = 0
#         for k in range(index - 1, -1, -1):
#             if arr[k] // 10 > 0:
#                 arr[k + arr[k] // 10] = arr[k] % 10
#                 arr[k] = 0


# 法2
class Solution(object):
    def duplicateZeros(self, arr):
        n = len(arr)
        count = 0
        index = 0
        while index < n - count:
            if arr[index] == 0:
                count += 1
            index += 1

        if index + count > n:
            arr[-1] = 0
            right = n - 2
            index -= 2
        else:
            right = n - 1
            index -= 1
        for i in range(index, -1, -1):
            if arr[i] == 0:
                arr[right] = 0
                right -= 1
                arr[right] = 0
                right -= 1
            else:
                arr[right] = arr[i]
                right -= 1


data = Solution()
arr = [8, 4, 5, 0, 0, 0, 0, 7]
print(data.duplicateZeros(arr))
arr = [0, 0, 0, 0, 0, 0, 0]
print(data.duplicateZeros(arr))
